package p1;

public class A {

	public C c;
	public long k(int a){
		return 49;
	}
	
	protected long k(long a){
		return 30;
	}
	
	
	public int[] selectionSort(int[] data){
		int lenD = data.length;
		int j = 0;
		int tmp = 0;
		for(int i=0;i<lenD;i++){
			j = i;
			for(int k = i;k<lenD;k++){
				if(data[j]>data[k]){
					j = k;
				}
			}
			tmp = data[i];
			data[i] = data[j];
			data[j] = tmp;
		}
		return data;
	}


	public int[] InsertionSort(int[] data){

		int len = data.length;

		int key = 0;

		int i = 0;

		for(int j = 1;j<len;j++){

			key = data[j];

			i = j-1;

			while(i>=0 && data[i]>key){

				data[i+1] = data[i];

				i = i-1;

				data[i+1]=key;

			}

		}

		return data;

	}

	public int[] bubbleSort(int[] data){

		int lenD = data.length;

		int tmp = 0;

		for(int i = 0;i<lenD;i++){

			for(int j = (lenD-1);j>=(i+1);j--){

				if(data[j]<data[j-1]){

					tmp = data[j];

					data[j]=data[j-1];

					data[j-1]=tmp;

				}

			}

		}

		return data;

	}

	public int[] quickSort(int[] data){

		int lenD = data.length;

		int pivot = 0;

		int ind = lenD/2;

		int i,j = 0,k = 0;

		if(lenD<2){

			return data;

		}

		else{

			int[] L = new int[lenD];

			int[] R = new int[lenD];

			int[] sorted = new int[lenD];

			pivot = data[ind];

			for(i=0;i<lenD;i++){

				if(i!=ind){

					if(data[i]<pivot){

						L[j] = data[i];

						j++;

					}

					else{

						R[k] = data[i];

						k++;

					}

				}

			}

			int[] sortedL = new int[j];

			int[] sortedR = new int[k];

			System.arraycopy(L, 0, sortedL, 0, j);

			System.arraycopy(R, 0, sortedR, 0, k);

			sortedL = quickSort(sortedL);

			sortedR = quickSort(sortedR);

			System.arraycopy(sortedL, 0, sorted, 0, j);

			sorted[j] = pivot;

			System.arraycopy(sortedR, 0, sorted, j+1, k);

			return sorted;

		}

	}

	public int[] mergeSort(int[] data){

		int lenD = data.length;

		if(lenD<=1){

			return data;

		}

		else{

			int[] sorted = new int[lenD];

			int middle = lenD/2;

			int rem = lenD-middle;

			int[] L = new int[middle];

			int[] R = new int[rem];

			System.arraycopy(data, 0, L, 0, middle);

			System.arraycopy(data, middle, R, 0, rem);

			L = this.mergeSort(L);

			R = this.mergeSort(R);

			sorted = merge(L, R);

			return sorted;

		}

	}



	public int[] merge(int[] L, int[] R){

		int lenL = L.length;

		int lenR = R.length;

		int[] merged = new int[lenL+lenR];

		int i = 0;

		int j = 0;

		while(i<lenL||j<lenR){

			if(i<lenL & j<lenR){

				if(L[i]<=R[j]){

					merged[i+j] = L[i];

					i++;

				}

				else{

					merged[i+j] = R[j];

					j++;

				}

			}

			else if(i<lenL){

				merged[i+j] = L[i];

				i++;

			}

			else if(j<lenR){

				merged[i+j] = R[j];

				j++;

			}

		}

		return merged;

	}

	public int[] shellSort(int[] data){

		int lenD = data.length;

		int inc = lenD/2;

		while(inc>0){

			for(int i=inc;i<lenD;i++){

				int tmp = data[i];

				int j = i;

				while(j>=inc && data[j-inc]>tmp){

					data[j] = data[j-inc];

					j = j-inc;

				}

				data[j] = tmp;

			}

			inc = (inc /2);

		}

		return data;

	}

	
}
